\documentclass[10pt, oneside,a4paper]{report}
\usepackage[latin1]{inputenc}
\usepackage{paralist}
\usepackage{amsmath}    %ѧ֧
\usepackage{amssymb}    %ѧ֧
\usepackage{txfonts}    %ַ֧
\usepackage{graphicx}   %bmpjpgepsͼ֧
\usepackage{CJK}        %֧
\usepackage{color}
\usepackage{enumerate}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{pseudocode}
\usepackage{hyperref}

\graphicspath{{figures/}}

\begin{document}

\lstset{ %
  language=C,                			% choose the language of the code
  basicstyle=\small\ttfamily,			% the size of the fonts that are used for the code
  % numbers=left,                   	% where to put the line-numbers
  % numberstyle=\footnotesize,      	% the size of the fonts that are used for the line-numbers
  % stepnumber=2,                   	% the step between two line-numbers. If it's 1 each line 
  % will be numbered
  % numbersep=5pt,                  	% how far the line-numbers are from the code
  keywordstyle=\color{blue!70},
  % commentstyle=\color{red!50!green!50!blue!50},
  commentstyle=\color{olive},
  stringstyle=\color{purple},
  keywordstyle=\color{blue}\bfseries,
  directivestyle=\color{blue},  
  frame=shadowbox,
  rulesepcolor=\color{red!20!green!20!blue!20},
  backgroundcolor=\color{white},  	% choose the background color. You must add \usepackage{color}
  showspaces=false,               	% show spaces adding particular underscores
  showstringspaces=false,         	% underline spaces within strings
  showtabs=false,                 	% show tabs within strings adding particular underscores
  % frame=single,	                	% adds a frame around the code
  tabsize=2,	        	        	% sets default tabsize to 2 spaces
  captionpos=b,                   	% sets the caption-position to bottom
  breaklines=true,                	% sets automatic line breaking
  breakatwhitespace=false,        	% sets if automatic breaks should only happen at whitespace
  title=\lstname,                 	% show the filename of files included with \lstinputlisting;
  % also try caption instead of title
  escapeinside={\%*}{*)},         	% if you want to add a comment within your code
  morekeywords={*,...}            	% if you want to add more keywords to the set
}


\begin{CJK*}{GBK}{song}

  \title{Implementation of COPE in NS-2}
  \author{Lianghui Ding\\
    Signal and Systems, Uppsala University, Sweden\\
    lianghui.ding@angstrom.uu.se}
  \maketitle
  \newpage
  
  \phantomsection
  \tableofcontents
  \listoffigures
  \listoftables
  \newpage

  \chapter{Background of COPE}

  COPE is proposed by S. Katti \textit{et.al.} in MIT and published in both SIGCOMM 06~\cite{nc-xor-sigcomm06} and IEEE Transactions on Networking 08~\cite{NC-XOR-Katti-TON-08}. COPE is the first implementation of inter-session network coding in a real testbed and shows significant performance gain. The aim of COPE is to bridge the bridge the theory of network coding with practical application.

  COPE is implemented in a real testbed with $20$ laptops. COPE is implemented using the Click Toolkit~\cite{network-clicktoolkit-mit-00} in Linux and evaluated in an IEEE 802.11a network. However, the source code of COPE is not open and it is also not easy for every interested researcher to implement a similar testbed as them. Therefore, we implement COPE in the network simulator, ns2, to evaluate its performance with different network configurations.

  The key idea of COPE is making use of one-hop network coding to reduce the number of transmissions to save transmission time and scare wireless resources. Several packets are sent together with network coding to multiple nexthop nodes, which can correctly decode it.

  \chapter{Details of COPE}
  In general, COPE includes three parts: (i) Opportunistic Listening; (ii) Opportunistic Coding and (iii) Reception Reports.

  \section{Opportunistic Listening}
  Opportunistic listening is to increase opportunities of network coding. All nodes listen to the wireless channel all the time and receive all packets and try to decode them whether the packets are intended to them or not.

  \section{Opportunistic Coding}
  Opportunistic coding is the method of finding the coding packets. Network coding happens among neighboring nodes, which have redundancy information to decode the coded packet. When a node gets the wireless channel, it needs to choose packets for coding from local buffers. Since there may exist many choices of network coding, COPE builds up several rules for coding packet selection.

  \begin{itemize}
  \item
    Coding native packets only.
  \item
    Coding as more packets as possible to maximize the gain of network coding.
  \item
    The total decoding probability of all nexthop nodes is larger than a threshold $G$ (By default, $G=0.8$).
  \item
    Never delaying packets. The packet at the head of the output queue has to be included in the transmission.
  \item
    Never coding packets to the same nexthop.
  \end{itemize}

  \section{Reception Report}
  The transmitting node selects coding packets according to what packets the nexthop nodes have. There are two ways through which the transmitting node obtains information about packets in nexthop nodes.

  One is reception report, in which both piggyback report and periodical report are employed.

  The other is guessing, which guesses the probability of overhearing the packet at the nexthop nodes leveraging routing protocols.

  \chapter{Implementation of COPE in NS-2}
  We need to implement three key parts of COPE as well as some complementary parts for IEEE 802.11 network, namely, pseudo-broadcast, asynchronous acknowledgement and retransmission. We will mainly modify IEEE 802.11 MAC and the IFQ protocol stacks in NS-2. Major network coding is done in IFQ.

  \section{Opportunistic Listening}
  In current ns-2, the received packet will be dropped if the received signal strength is less than a certain threshold or the node is not the intended receiver of the packet, while we have to keep all packets received for network coding later on.

  Thus, we need to modify the packet receiving mechanism in MAC layer. All packets now are transferred up to the input queue. If the node is the intended receiver, the packet will be transferred up to routing layer or transport layer by IFQ. Otherwise, the packet will be kept in a new backup queue.

  I think most of this part has been done.

  \section{Opportunistic Coding}
  In current ns-2, if the MAC layer gets a packet to transmit, it will contend for the channel. After the packet has been transmitted, the MAC layer will refetch a new packet from COPE(ifq), will be transferred to MAC layer. Hence, there is only loose coupling between these two layers in current ns-2.

  With network coding, COPE, when the MAC layer catches the channel, it needs to inform the IFQ to do opportunistic network coding.  We can realize it in this way. First, the IFQ transfers the packet as in legacy ns-2; Second, when the MAC layer catches the channel, it informs IFQ; Third, the IFQ looks for opportunistic coding opportunity and sends a newly organized packet to MAC layer.

  As to how to find the opportunistic network coding scheme, we can realize it as in COPE. We maintain two virtual queues, one for long packets, and the other for short ones. The packets for each nexthop node in each queue may be realized with linked list refer to the realization of queues in ns-2. (\textit{I'm not sure about that and will check it later on. L:Yes,it's LinkList!})

  The most tricky rule of opportunistic network coding is to guarantee the probability of decoding, which depends on guessing. In COPE implemented in the testbed, the probability of overhearing leverages the routing protocol. However, we are going to realize it in a different  and simpler way. The overhearing probability of calculated by smoothing historical records. Assuming the probabilities in last and current report periods are $p_l$ and and $p_c$, respectively, we can calculate the updated overhearing probability as
  \begin{equation}
    p_u = p_l + \alpha\times\frac{t}{T}\times p_c
  \end{equation}
  where $\alpha$ is the moving weight, $t$ is the time between last and current reports and $T$ is the reference period.

  With this method, we will not need any help from the routing layer and generalize the application area of COPE.

  \section{Reception Report}
  Reception report include two parts, namely, piggyback report and periodical report.

  Piggyback report can be done after opportunistic coding is fixed in IFQ.

  Periodical report can be done by setting a timer in IFQ. When the MAC layer is idle for transmission and there is no new packet in the queue in IFQ, the timer is started. The timer will be reset by new packet arrival or periodical report. The timeout will trigger a periodical report if there are newly received packet. This is what proposed in COPE.

  \section{Pseudo Broadcast}

  Pseudo-broadcast is to select one of the intended receivers in the coded packet as the receiver returning ACK. How to select the one is not clear in COPE. Here, we can select the receiver of the oldest packet as the receiver returning ACK.

  \section{Asynchronous Acknowledgement and Retransmission}
  Asynchronous acknowledgement is done in IFQ after reception report is fixed. To do this, we need a record of decoded packets without acknowledgements.

  When a node receives a negative acknowledgement (NACK), it will put the packet at the head of the queue and retransmit it again.

  In ns-2, the maximum number of retransmissions is controlled at the MAC layer, since a packet is retransmitted immediately after receiving NACK. With COPE, the situation is complicated, the transmitted packet is saved in a queue now and the retransmission maybe after other packets have been transmitted. Thus, we have to record the number of retransmissions of each packet in the queue.

  \section{Packet Reception}
  If a node receives a packet, it will transfers it to IFQ, and IFQ decodes it if possible. Otherwise, the coded packet will be dropped by IFQ directly.

  \chapter{Task Allocation}
  \begin{table}[h]
    \begin{tabular}{|c|c|c|}
      \hline
      Common parts & Part I & Part II\\
      \hline
      Definition of packet head & Opportunistic coding & Reception Report\\
      \hline
      Definition of functions & Decoding & Asynchronous ACK\\
      \hline
      Definition of queues &  & Retransmission\\
      \hline
    \end{tabular}
  \end{table}

  \chapter{Tasks Implementation}

  \section{Definition of Packet Header}
  The header of COPE is defined according to the structure the paper provides, except the first block (packets XOR-ed together). For each native packet, a local packet sequence number (\textit{Local\_PKT\_SEQ\_NUM}) has been added, to let the receiver to know which packet to acknowledge.

  For each native packet in the encoded packet, the header lists its ID (\textit{PKT\_ID}), which is a 32-bit hash of the packet's source IP address and IP sequence number. This IP sequence number means the number of native packets, including native packets both directly sent and the ones encoded, sent from this node.

  \begin{figure}[htb]
    \centering
    % \includegraphics[width=4in]{cope_packet_header.eps}
    \caption{COPE Packet Header}
    \label{cope_packet_header}
  \end{figure}

  Note that IP sequence number is totally different from the local sequence number \textit{Local\_PKT\_SEQ\_NUM}. IP sequence number is the number of native packets sends from this node to one node or several nodes, but the local sequence number \textit{Local\_PKT\_SEQ\_NUM} is the number of native packets sends to one specific neighbor.


  \section{Definition of COPE}
  \textit{COPE} (\textbf{refer to Figure 1})is the main IFQ proxy which works as a IFQ entry and interacts with \textit{LL} and \textit{MAC}, it also contains Main logical algorithm for the whole encoding and decoding process. With all queues and timers encapsulated inside, \textit{COPE} instance is created for each node by tcl/tk. Once \textit{COPE} receives a packet from \textit{LL}(it's upper layer), it will transfer the packet to the real IFQ(\textit{COPEPriQueue}) to encode the native packet, while if the packet is received from MAC with 'UP' direction, \textit{COPE} will decode it directly. This is because our one-queue dual-access design for \textit{COPEPriQueue}, refer to \textit{COPEPriQueue} description in 'Definition of Queues' section for detail.

  \begin{figure}[htb]
    \centering
    \includegraphics[width=4in]{COPE.eps}
    \caption{COPE Structure}
    \label{cope_structure}
  \end{figure}

  \section{Definition of Queues}
  Each node maintains several queues, including one NonAckQueue, one AckPendQueue, one PacketPool, one PacketInfo and one ProbGuess.
  \subsection{COPEPriQueue}
  \textit{COPEPriQueue} is the real IFQ which multi-inherit from \textit{CMUPriQueue} and \textit{PriQueue} as showed in the following class graph(\textbf{Figure 2}). Although ns2 use different ifq for different routing protocols, here we just integrate both of them together and overwrite some of their functions.
  \begin{figure}[htb]
    \centering
    \includegraphics[width=5in]{class_inherit_graph.eps}
    \caption{Class Graph for COPEPriQueue}
    \label{class graph for COPEPriQueue}
  \end{figure}
  As you see in the graph, both queues are also inherit from a common class \textit{Connector} which will result in an ambiguous function call, so we need to indicate a specific path while using \textit{Connector}'s members or functions.

  Another problem is that we design the IFQ much more like a BiConnector rather than just a Connector, because all packets sent up from Mac layer will go through \textit{COPE} prior to LL, so that \textit{COPE} can decode the incoming packet firstly. In order to simplify this class heritant system, merely simulating the a BiConnector by adding a uptarget\_ member is enough, this means it's not necessary to use a queue to store all 'UP' packets, but decode them and send out directly, thus only one \textit{COPEPriQueue} for all 'DOWN' packets is implemented, so called one-queue dual-access design for IFQ.



  \subsection{NonAckQueue}
  NonAckQueue is used to store all native packets, which are in the encoded packet, sent out from this node, but have not been acknowledged. In other words, the unencodable packets (control packets and non-encoded packets) would not be put into NonAckQueue.

  \begin{lstlisting}[language=C]
    typedef struct {
      u_int16_t local_seqnum; // local sequence number of Non-Acked pkt
      u_int8_t rcounter; // counter for times of retransmission
      Packet* ppkt; // pointer to packet
    } non_ack_entry_t;
    
    typedef struct {
      int nodeid; // next hop
      list<non_ack_entry_t>* entries;
    } non_ack_t;
  \end{lstlisting}
  
  Whenever OutputQueue sends out a native packet, which is included in the encoded packet, this native packet is put into the NonAckQueue, at the same time, COPE starts a timer for this native packet. The time for timeout is a little longer than the Round Trip Time (RTT). We call this timer NonAckTimer, which inherits from CopeTimer. If the acknowledgment of this native packet comes back before the timer expires, the COPE stops this timer and delete this native packet from NonAckQueue. Otherwise, this native packet will be retransmitted, by putting it at the head of OutputQueue. And immediately, set a new timer for this native packet and increase the retransmission counter by one. When OutputQueue sends it out, it checks the counter, if counter == 2 (retransmission threshold is 2 by default), then stop its timer and drop this packet.

  \subsection{AckPendQueue}
  Each node maintains an AckPendQueue, each AckPendQueue has this node's neighbors' ACK information. AckPendQueue is implemented as a linked list, whose node's structure looks like this:

  \begin{lstlisting}[language=C]
    #define ACKMAP_TOTAL_SIZE     256
    
    typedef struct {
      int neighbor; //MAC address of the neighbor
      u_int16_t lastack; // last ack sequence number
      u_int16_t shifts; // number of bits shifted
      u_int8_t rtimes; // number of retransmission times
      bitset<ACKMAP_TOTAL_SIZE> ackmap;
    } ack_pend_t;
  \end{lstlisting}

  \subsubsection{Enqueue Pending ACKs}
  When one node receives an encoded packet, if this packet is decodable, the node immediately schedules an ACK event for the decoded native packet, by putting its previous hop's MAC address and local sequence number into AckPendQueue. There are four cases when enqueue a new pending ACK:

  \begin{itemize}
  \item \textbf{New Neighbor}
    There is no packet from that neighbor in the AckPendQueue right now, maybe this is the first packet of that neighbor arrived, or the previous packets have been out of date and removed??. So create a new node in the linked list and push it back with the packet's pending ACK information.

  \item \textbf{New Pending ACK}
    The neighbor sends this packet is already in the list, then find the existing neighbor and enqueue the pending ACK.

  \item \textbf{Duplicate Pending ACK}
    The neighbor sends this packet is already in the list, but this is a duplicate pending ACK. Which means the last pending ACK has not sent out, or the last ACK lost, so trigger an event to re/transmit this pending ACKs.

  \item \textbf{Out-of-date Pending ACK}
    This could happen when the incoming packet's local sequence number is smaller than the number of bits shifted for this neighbor. This data packet comes after shifting the corresponding bit, maybe it has been acknowledged or retransmitted for more than two times, so ignore it.
  \end{itemize}

  After enqueueing, if the number of pending ACKs in the AckPendQueue for that neighbor is more than eight, then trigger an event to send pending ACKs. In addition to that, if there is a duplicate pending ACK in the queue, which means the neighbor may not receive the previous asynchronous ACKs. So also trigger an event to retransmit the pending ACKs, at the same time increase the retransmission counter by 1. Because the sender retransmit the data packet only two times, if the receiver still not receive the packet, the sender gives up and drops the packet. So if the counter is over the retransmission timers, the receiver dose not wait for this packet any more, the AckPendQueue remove this packet's pending ACK information, and ignore this packet from that time. When sending out a data packet, it should firstly check if there is any ack pending event for that neighbor (next hop). If that, append that neighbor's ack pending information (hdr\_ack\_t).

  \subsubsection{Get ACKs}
  There are two situations need to get ACKs. Firstly, when the node has data packet to send out, it checks whether there is any pending ACKs to transmit, if so, it appends them to the COPE header. Secondly, when there is no data packet to send out, then broadcast periodic special control packet, which contains the ACK block.

	The pending ACKs for the neighbors store in the bitmap of the linked list. But how to get the right ACKs is a little tricky. Hopefully, the following pseudo code may be helpful:

  \begin{pseudocode}[ruled]{<GET\_PENDING\_ACKS>}{<x>}
    \COMMENT{Get pending ACKs of neighbor $x$ from AckPendQueue $q$} \\
    \COMMENT{Look-up this neighbor $x$'s entry $e$ in $q$} \\
    e = q \rightarrow lookup(x) \\
    \IF e\ \verb!==!\ NULL \THEN
    	\RETURN {NULL} \\
    
    hdr\_ack\_t* ack \\
    ack \rightarrow neighbor\_ = x \\
        
    \IF e \rightarrow rtimes > RT\_TIMES \THEN
    	\BEGIN
    		e \rightarrow ackmap[0] = 1 \\
    		e \rightarrow rtimes = 0
    	\END
    
    \\ i = 0 \\
    \WHILE e \rightarrow ackmap[i]\ != 0 \DO
    	i\ \verb!++! \\
    
    \IF i == 0\ \verb!&&!\ e \rightarrow lastack - e \rightarrow shifts > 0 \THEN
    	e \rightarrow rtimes\ \verb!++!
    \ELSEIF i > 0 \THEN
    	\BEGIN
    		e \rightarrow ackmap\ \verb!<<=!\ i \\
    		e \rightarrow shifts\ \verb!+=!\ i
    	\END
    
    \\ num = e \rightarrow lastack - e \rightarrow shifts \\
    \IF num > ACKMAP\_SIZE \THEN
    \BEGIN
    	\COMMENT{Get $ACKMAP\_SIZE$ bits from $ackmap$, starts from the first bit} \\
    	ack \rightarrow ack\_map\_ = getbits(ACKMAP\_SIZE) \\
    	ack \rightarrow last\_ack\_ = e \rightarrow shifts + ACKMAP\_SIZE + 1
    \END
    \ELSE
    \BEGIN
    	\COMMENT{Get $num - 1$ bits from $ackmap$, starts from the first bit} \\
    	ack \rightarrow ack\_map\_ = getbits(num - 1) \\
    	ack \rightarrow last\_ack\_ = e \rightarrow lastack
    \END \\
  	\RETURN{ack}
  \end{pseudocode}

  \subsection{PacketPool}
  PacketPool (\textit{Packet Pool}), in which it keeps a copy of each native packet it has received or sent out. And this Packet Pool is garbage collected every few seconds. The structure of the PacketPool consists of one hash table, one first-in-first-out (FIFO) queue (backup queue), and one reception report list.

  \begin{itemize}
  \item \textbf{Hash Table}

    \begin{lstlisting}[language=C]
      typedef struct {
        int pktid; // packet id
        Packet* ppkt; // pointer to the packet stored in backup_queue_
        UT_hash_handle hh; // uthash: hash table handler
      } pkt_entry_t;
    \end{lstlisting}

    To store native data packets keyed on packet id and the buckets of the hash table is the pointer of the packet corresponding to this packet id. It's easy for COPE to do decoding when receives an encoded packet, because COPE could quickly get the corresponding packet through its id.2

  \item \textbf{Backup Queue}
    To store packet pointers with FIFO strategy using the linked list. The purpose of this backup queue is to assist the process of garbage collection.

  \item \textbf{Reception Report List}

    \begin{lstlisting}[language=C]
      #define BITMAP_TOTAL_SIZE 256
      #define BITMAP_SIZE 8
      
      typedef struct {
        nsaddr_t srcip; // source ip
        u_int16_t lastpkt; // ip sequence number
        u_int16_t pre; // last ip seq number will be expired in next period
        u_int16_t next; // last ip seq number will be expired in next next period
        u_int16_t shifts; // number of bits shifted
        bitset<BITMAP_TOTAL_SIZE> bitmap; // bit-map of recently heard packets
        bool gc; // flag, has done the garbage collection or not
      } report_t;
    \end{lstlisting}

    To record which packets have been received from which neighbor, and also which packets would be expired in the coming period, and be delete from Packet Pool during the garbage collection process. This list is also the source of periodic reception reports.
  \end{itemize}

  \subsubsection{In Pool}
  When one native packet has received or sent out, put this packet into the PacketPool. The procedure of doing that looks like this:

  \begin{itemize}
  \item Firstly, check whether this packet has been in the pool or not. If already been, then ignore it. In addition, check whether this packet has been garbage collected before. If so, then ignore it too.
  \item Secondly, push this packet into the backup queue.
  \item Thirdly, add this packet's information into the hash table.
  \item Finally, update the reception report list according to this packet.
  \end{itemize}

  \begin{pseudocode}[ruled]{<IN\_POOL>}{<Packet * p>}

  \end{pseudocode}

  \subsubsection{Get Reception Report}
  There are also two situations need to get reports, just like getting ACKs from AckPendQueue. Firstly, when the node has data packet to send out, it checks whether there is any reception report to transmit, if so, it appends them to the COPE header. Secondly, when there is no data packet to send out, then broadcast periodic special control packet, which contains the reception reports.

  The whole procedure of getting reception as follows:

  \begin{pseudocode}[ruled]{<GET\_REPORT>}{<nsaddr_t srcip>}
    
  \end{pseudocode}

  \subsubsection{Garbage Collection}
  Without appropriate approach to clear the out-of-date packets in the pool, the pool will soon overflow. That's why the garbage collection is used. The garbage collection is executed by COPE very few seconds.
  
  \begin{pseudocode}[ruled]{<GARBAGE\_COLLECTION>}{<void>}
    
  \end{pseudocode}  

  \subsection{PacketInfo}
  Each node keeps a hash table, \textit{packet info}, that is keyed on packet id. For each packet in the output queue, the table indicates whether each neighbor has that packet or not.

  Using the \textit{uthash} as the hash table implementation, where \textit{uthash} is an easy-to-use hash table for \textit{C} structures.

  As said before, the hash table should keyed on packet id, however, to get faster access speed and better performance, the structure key (\textit{info\_key\_t}, as showed bellow) is used rather than the packet id.

  \begin{lstlisting}[language=C]
    /* this is the key of the hash table */
    typedef struct {
      int pkt_id;
      int nodeid;
    } info_key_t;
    
    /* the real hash table entry */
    typedef struct {
      info_key_t* key;
      bool prob; 
      UT_hash_handle hh;
    } packet_info_t;
  \end{lstlisting}

  That's because if the hash table is keyed on packet id, then each bucket in hash table is a \textit{linked list} structure, of which each element is composed of node id and the probability (type of \textit{bool}, true indicates the neighbor has that packet, false means not). When the sender wants to do encoding process and gets one neighbor's probability of having that packet, it has to search the whole list for each packet, which wastes time and resources. If the \textit{info\_key\_t} is used as key, the probability of each neighbor having that packet is one entry of the hash table. That means the sender can get each neighbor's probability with high speed, which is the main advantage of hash tables over other table data structures.

  \subsection{ProbGuess}

  \begin{itemize}
  \item {\textit{General Ideas}}
  \end{itemize}

  After searching for the packet info, if the node is still not sure whether its next hop has a specific packet or not, a probability guessing mechanism should be utilized.

  The guessed probability is only used at the the encoding-needed node(subset of intermediate nodes), as a prob demander, the node will maintain an instance of \textit{ProbGuess} to update probs after packet info is updated and fetch a specifi\textbf{ General Ideas }c prob from. To explain how probability guessing works and what's the implementation idea, we can consider a simple network scenario firstly as \textbf{Figure 3}:

  \begin{figure}[htb]
    \centering
    \includegraphics[width=3.5in]{probguess-scenario.eps}
    \caption{Butterfly Topology}
    \label{butterfly_topo}
  \end{figure}

  In the above simple topology, it's obvious that A and C are source nodes with data flow A-B-E-F and C-B-E-F seperately, both B and E probably encode a native packet. Assume that A has sent out packets with sequence number 1, 2, 3 and so does C, E has received all these packets and keeps them in the \textit{COPEPriQueue}, then we can compute the new probability at E by this way:

  E maintains a table for each source ip and the entry of each table is keyed by all its neighbor nodes, at a certain time point, E receives a reception report and update the table into the following status(see Figure 3, with V:exist, X:non-exist ) according to several important rules:

  \begin{figure}[htb]
    \centering
    \includegraphics[width=3.5in]{probguess-status.eps}
    \caption{Neighbors' Packet Status}
    \label{neighbor_pkt_status}
  \end{figure}

  \begin{enumerate}
  \item 
    for each source ip, only update status of the packets from the smallest sequence number to the largest sequence number defined by packets in the \textit{COPEPriQueue}. (A1 to A3, C1 to C3 in the example)
  \item
    if I am the host node, status of all packets in my \textit{COPEPriQueue} should be 'V', since I have them all.(A1 to A3, C1 to C3 in the example)
  \item
    if a neighbor is the source node or previous hop, it's definately that he has that packet.(node A and B has A1, A2, A3 for sure in the example)
  \item
    if a neighbor has sent a valid reception report, noticing that he has a specific packet or not, the corresponding status should be updated.(D's reception report said that he has A1, A3 but A2 in the example)
  \item
    if a neighbor is the desination, he shouldn't has this packet. (F's status for A1, A2, A3 is 'X' in the example)
  \item
    otherwise, status should be 'X' by default.

  \end{enumerate}
  Thus, we can easily calculate a probability p\_c for each source ip (p\_c(D,A) = 2/3, p\_c(F,C) = 1/3), which means node D has any packet originated from source A with 2/3's probability and same meaning for p\_c(F,C). As you may realize, instead of evaluating each packet's probability, we just evaluate the probability of a set of packets sourced by a specific node.

  Until now, we always skip a fact that the probability is updated continuously, to increase the accuracy of the guessed probability, we should consider historical records as a factor and design an algorithm to compute probability accumulately, so a formula(as mentioned above, in "Implementation of COPE in NS-2/Opportunistic Coding") based on Moving Weighted Average Method which also regards updating time peroid as a coefficient is very helpful.

  Let's elaborate the network scenario described before, further assuming that at node E, node D's last reception report arrived at $T_0$ while the current report time is $T_1$, $T_0$ is considered as history and will be updated time by time, also node D's last updated probability for source A is p\_l(D,A), T is the periodical report duration, alpha is an adjusting factor. Then, the updated probability should be \begin{equation} p_u[D,A] = p_l[D,A] + \alpha\times\frac{T_1 - T_0}{T}\times p_c[D,A] \end{equation} according to that designed formula.

  Throughout the above description, if the calculated probability smaller than G(0.8 here), we judge the packet is impossible to be in this neighbor.

  \begin{itemize}
  \item {\textit{Implementation Details} }
  \end{itemize}

  Firstly, to record all probability information, a hash table should be constructed with a self-defined key. An updating operation will result in the modification of one entry in this prob\_info\_table and the node will get a desired probability from here too.

  \begin{lstlisting}[language=C]
    typedef struct {
      int nodeid;
      int src_ip;
    } prob_key_t;

    typedef struct {
      prob_key_t* key;
      uint8_t prob;    
      UT_hash_handle hh;
    } prob_info_t;
  \end{lstlisting}

  Second, since packets set in \textit{COPEPriQueue} is changable all the time, everytime a new reception report is received, the node should modify a consistent start and end sequence number for each source ip, then count the total number of packets (eg. 3 from source A in the scenario). At the same time, also count the number of packets in a certain neighbor's reception report(eg. 2 for node D from source A in the scenario), thus we can derive a current probability. A new structure can be used as an assistant for this process, and a list of instances of this structure are created in the runtime.

  \begin{lstlisting}[language=C]
    typedef struct {
      nsaddr_t src_ip;
      uint16_t start_seq_num;
      uint16_t end_seq_num;
      int pkt_count;
    } src_info_t;
  \end{lstlisting}

  Third, to record the historical updating time for each neighbor, a simple struct is designed and similarly create a list of instances according to different neighbor node.

  \begin{lstlisting}[language=C]
    typedef struct {
      int nodeid;
      double last_report_time;
    } nb_info_t;
  \end{lstlisting}

  Fourth, two iterfaces are provided. one is to update prob\_info\_table\_ after updating packet\_info, which means a reception report received. This function will execute the following works:

  \begin{enumerate}
  \item 
    update the src list information according to the large and small virtual queue, since the source nodes are determined while initialization, no need to change(insert/delete) the list elements dynamically. 
  \item
    update nb\_id's nb\_info\_t, if it exists, delet add a new nb\_info\_t to the list, now one little problem still exists that nothing to do if a node is no longer its neighbor.
  \item
    get the new pkt\_info, and compute a new prob with the above strategy
  \item
    update the new prob in prob\_info\_table, if the updated entry exists, delete it and insert a new one
  \item
    reset the src list to a default status

  \end{enumerate}

  Another get\_prob\_info will simply search for the hash table according to a specific source and neighbor, if no entry exists, return zero as the probability. 

  \begin{lstlisting}[language=C]
    void  up_prob_info(int nb_id,  
    neighbor_list_node* neighbor list, 
    VirQueue* virtual table,
    PacketInfo* pkt_info);
    
    double get_prob_guess(int src ip, int neighbor id); 
  \end{lstlisting}


  \subsection{VirQueue}
  The virtual queue is used to store all packets' pointer in the \textit{COPEPriQueue}, sorted by the next hop and packet type(Large/Small) pair. So a new hash table is constructed with a specific virtual key, each entry stores a packet queue which maintains all qualified packets.
  \begin{lstlisting}[language=C]
    typedef struct {
      int nb_id;
      bool type;
    }vir_key_t;
    
    typedef struct {
      vir_key_t key;
      PacketQueue * pkt_q; 
      UT_hash_handle hh; 
    } vir_entry_t;
  \end{lstlisting}

  There are three main interfaces for \textit{VirQueue}, the first one is inserting a packet into the virtual table after inserting into the output queue, the related entry is specified by next\_hop id and packet size, if no entry exist, creat it dynamically, the bool parameter is to decide enque head or push back; the second one is getting a virtual packet matching the passed parameters; the third one will remove a packet from the virtual table, if the packet queue becomes empty after removing, just naturally delete the whole entry.

  \begin{lstlisting}[language=C]
    void enque_vir_pkt(Packet * p, bool rt);
    
    PacketQueue * get_vir_pktq(int node_id, char type);

    void remove_vir_pkt(Packet * p);
  \end{lstlisting}


  \section{Timers}
  Each node maintains following timers to control the packet retransmission, periodic control packets, and reception reports, etc.

  \subsection{CopeTimer}
  CopeTimer is the parent class of other timers in COPE, which inherits from Handler. CopeTimer provides some virtual member functions for child classes.

  \subsection{NonAckTimer}
  NonAckTimer is used to manage the packet retransmission. Each NonAckTimer is started for each native packet in the encoded packet when sent out. If the acknowledgment comes back before the timer expires, the packet in the NonAckQueue is remove, and the timer of this packet is stopped. Otherwise, the timer expires. Then the retransmission process is called, by getting out that packet from NonAckQueue and retransmitting it, increasing the retransmission counter by 1, then starting a new timer for this packet.

  Note that, to identify which timer, the neighbor's ID and local sequence number in that packet have been recorded when starting timer for it. These two variables are used to decide which timer should be stopped when receiving ACKs.

  \subsection{CtrlPktTimer}
  There are some periodic control packets, reception reports and pure ACK packets in COPE, that why this CtrlPktTimer exists. This timer is started when the OutputQueue is empty, and stopped when the OutputQueue contains packets. When the timer expires, the control packets are sent out.

  \section{Opportunistic Listening}
  COPE exploits the shared nature of the wireless broadcast medium, creating many opportunities for nodes to overhear packets. Each node snoops on all communications over the wireless medium and store the overheard packets for a limited period \textit{T} (the default is \textit{T = 0.5s}).

  In addition, each node acknowledges which packets it has heard by piggybacking the data packets the node transmits, which is called \textit{reception report} in this paper. If a node has no data packets to transmit, it periodically sends the reception reports in special control packets.

  As for implementation in NS-2, inheriting from \textit{Class Tap} should be a good choice, which minimizes the changes of NS-2. There the \textit{Class Tap} is left to tap out all data packets (both encoded and native) received at this host and promiscuously snoop them for interesting tidbits. However, the problem cannot be solved by inheriting, because there is another \textit{Agent DSRAgent} inherits from \textit{Class Tap}. When these two subclasses use the same member element in super-class, which causes some problems. Considering these situations, the solution is: add one more variant of \textit{Class Tap}, which is used to handle all the COPE related incoming packets.

  \section{Opportunistic Coding}

  Each node create a \textit{COPE} instance which will further create a lot of assistant queues, handlers and even timers in its init function. All encoding algorithm is implemented in COPE as mentioned before, to elaborate how encoding process is realized, we can refer to the following sequence diagram which simulates a packet \textit{p} received at a node: 

  \begin{itemize}
  \item
    \textit{COPE} receives \textit{p} with its direction 'DOWN'(\textbf{1}), it will firstly set the packet id and cope sequence number to the packet's header(\textbf{2}) if this is the source node, then call \textit{COPEPriQueue}'s \textit{cope\_prq\_senddown} function(\textbf{3}).

  \item
    \textit{COPEPriQueue} push back \textit{p} and also enque \textit{p} 's pionter into the virtual table(\textbf{4}), then put this packet into \textit{PktPool} if this is the source node(\textbf{5}), call \textit{COPE}'s encode function(\textbf{7}) with a dequed packet which is from head of \textit{COPEPriQueue}(\textbf{6}).

  \item
    \textit{COPE} firstly get packets from virtual packet queue of all valid neighbors, then check each of them whether \textit{p} is encodable or not. To do this, it will 'ask' \textit{PktInfo} and \textit{ProbGuess} in order, either of them 'said' yes can directly lead this packet encodable. After this, \textit{COPE} will xor all candidate packets and append them into the cope header's xor field, then return this encoded packet \textit{res\_pkt}. Actually, this process is much more complicated than this, so a pseudo code in the following part may be more understandable.(\textbf{8} to \textbf{14})
  \end{itemize}
  
  \begin{pseudocode}[ruled]{<ENCODE>}{<Packet * p>}
    \COMMENT{ Encode a native packet p}\\
    Remained\_NbList \GETS {Neighbors} - {Nexthop(p)} \\
    Encoded\_PktList \GETS {p} \\
    \IF size~of~p <  PACKET\_SIZE\_THRESHOLD
    \THEN
    tag \GETS Small
    \ELSE
    tag \GETS Large\\
    
    \FOREACH get~node~N~in~Remained\_NbList \DO 
    \BEGIN
    prob \GETS 1.0\\
    q \GETS head~of~its~tag~Virtual~Queue\\
    \FOREACH packet~r~in~Encoded\_PktList \DO
    \BEGIN
    \IF Nextop(q)~has~r~in~local~PktInfo
    \THEN
    prob \GETS prob * 1.0
    \ELSE 
    \BEGIN
    get~the~probability~Pr~for~r~from~ProbGuess\\
    prob \GETS prob * Pr\\
    \END\\
    \IF prob <= G 
    \THEN
    \EXIT loop
    \END\\
    \IF ( prob > G) 
    \THEN
    \BEGIN
    p \GETS p~xor~q\\
    add~q~to~Encoded\_PktList\\
    delete~N~from~Remained\_NbList\\
    \END
    \END\\
    
    tag = !tag\\
    
    \FOREACH get~node~N~in~Remained\_NbList \DO 
    \BEGIN
    prob \GETS 1.0\\
    q \GETS head~of~its~tag~Virtual~Queue\\
    \FOREACH packet~r~in~Encoded\_PktList \DO
    \BEGIN
    \IF Nextop(q)~has~r~in~local~PktInfo
    \THEN
    prob \GETS prob * 1.0
    \ELSE 
    \BEGIN
    get~the~probability~Pr~for~r~from~ProbGuess\\
    prob \GETS prob * Pr\\
    \END\\
    \IF prob <= G 
    \THEN
    \EXIT loop
    \END\\
    \IF ( prob > G) 
    \THEN
    \BEGIN
    p \GETS p~xor~q\\
    add~q~to~Encoded\_PktList\\
    delete~N~from~Remained\_NbList\\
    \END
    \END\\

    assemble~p's~xored~header~with~infomation~from~Encoded\_PktList\\
    \RETURN p  

  \end{pseudocode}

  \begin{itemize}  
  \item
    \textit{COPEPriQueue} call \textit{COPE}'s function to append the pend acks and reception reports into \textit{res\_pkt}'s cope header, no matter \textit{res\_pkt} is a native packet or encoded one.(\textbf{15}, \textbf{18})

  \item
    \textit{COPE} get the pend acks from \textit{PendAckQueue}(\textbf{16}, \textbf{17}) and get the reception reports from \textit{PacketPool}, the process of generating pend acks and reception reports will be seperately described in implementation of \textit{PendAckQueue} and \textit{PktPool}(\textbf{19}, \textbf{20}).
  \end{itemize}

  \begin{figure}[htb]
    \centering
    \includegraphics[width=5in]{sequence_diagram_down.eps}
    \caption{Downside Packet Received}
    \label{sequence diagram for downside packet received}
  \end{figure}

  Until now, we have completely implement an encoding algorithm, any packet send down from upper(LL) layer must go through this whole process. However, many other features like setting timers for packet retransmission and periodical control packet etc. are not reflected in the above diagram. 

  Note that we are only considering a sub-optimal solution, which iterates all valid neighbors in \{Neighbors\}-\{NextHops\} with a random order , we keep the optimal solution an open function  and may extend it in our future works. For an optimal solution, we can design a try\-and\-back method to select a packet as a best encoded choice prior to others, thus, after all round iterations, the encoded packet must be an optimal one.
  
  \section{Decoding}
  In the same way, We can describe the decoding process by simulating a packet \textit{p} received at a node and a sequence diagram is added to help us understand the whole process clearly: 

  \begin{figure}[htb]
    \centering
    \includegraphics[width=5in]{sequence_diagram_up.eps}
    \caption{Upside Packet Received}
    \label{sequence diagram for upside packet received}
  \end{figure}

  \begin{itemize}
  \item
    \textit{COPE} calls its receivable(\textbf{2}) member function which will further call extract\_state\_report(\textbf{3}) to update local packetInfo(\textbf{4}) and probGuess(\textbf{5}), then extract\_acks(\textbf{6}) to merely delete ack item with $neighbor == my_node_id$ in non\_ack\_queue(\textbf{7}). Receivable function will return false(non-decodable or overheard packet) or  true(native or decodable).
    
  \item
    \textit{COPE} then calls its decode function(\textbf{8}) to iterate each item but in xored header field, the passed packets also include a copy of the original target packet, this is because if the packet is non-decodable, we can recover it back for some further operations. To execute decoding process, \textit{COPE} will check its local packetPool{\textbf{9}} confirming whether a xored packet exist or not(\textbf{10}). If the target packet is native or overheard, just return this function, otherwise, continue with other items in the xored header. In the end, \textit{COPE} clears all the xored header(\textbf{11}) if it is decodable.
    
  \item
    No matter it is receivable or not, just put the result packet into PacketPool(\textbf{12}). We keep all non-decodable packets for a further decoding possibility, which is regarded as an extention for latter works.
    
  \item
    Append an ack of the result packet into pendAcks if the received packet is decodable(\textbf{13})

  \item
    If the packet is receivable(native or decodable packet), update packetInfo for the native or decoded packet(\textbf{14}), since it is obvious that the previous hop definitely has this packet.
  \end{itemize}

  Note that the whole decoding process has no relation with \textit{COPEPriQueue} and \textit{VirQueue}, because once receiving a new packet with 'UP', \textit{COPE} just deal with it directly rather than enqueue that packet.

  \section{Reception Report}
  The node knows what packets its neighbors have through reception report. Each node announces to its neighbors the packets it stores in the Packet Pool. When there is a data packet sent out, try to append the reception report got from Packet Pool if it is available. If there is no data packets to send, the node sends the reception report periodically.


  \section{Asynchronous ACKs}
  In COPE, encoded packets require all nexthops to acknowledge the receipt of the associated native packets. For the synchronous approach to coded packets is highly inefficient, encoded packets are acknowledged asynchronously and cumulatively in COPE.

  Neighbors' pending acks are stored in the AckPendQueue, when sending out a packet, the node try to get pending ACKs in the AckPendQueue and append them to the COPE header. If the node has no data packets to transmit, it sends the ACKs in periodic control packets, just like the reception report.

  \section{Control Packet}
  1. Allocate the COPE control packet in the cope layer, with a type tag COPE\_CTRL/COPE\_DATA as the identifier.(for cope, all other packets are regarded as normal data packet). 

  2. reception Report Control packet and Acks control packet are bind together, which means once one of them is simulated to send out, the other type of field will also be assembled. 

  3. No need to encode the control packet, even enque it into IFQ, since it must be no packet no data packet in the queue at that time. Nope!!! what about the other trigger condition??? so should the control packet encoded?

  4. Start the control packet timer when the simulator run.

  5. If a node receives a control packet, after updating packet info and ack info, this packet should be dropped

  \section{Retransmission}
  There are two type of retransmission in COPE. One is retransmission of data packets, another is retransmission of asynchronous ACKs. 

  \begin{itemize}
  \item \textbf{Data Packet Retransmission}
    When the timer for the data packet in the NonAckQueue is expired, which means the nexthop does not receive that data packet. After the expiration, the NonAckTimer handler will be called to process the data packet retransmission. And the retransmission times is limited to 2 times, after that, the node gives up and drops that packet. So the COPE does not guarantee the reliability at link layer.

  \item \textbf{Asynchronous ACKs Retransmission}
    This is the counterpart of data packet retransmission. When the nexthop gets a duplicate data packet, which means the previous data packet lost, so the nexthop gets the ACKs from the lost one and append them to another data packet, then sends out. The retransmission times for data packet is limited to 2, so the retransmission times for asynchronous ACKs should be limited (2 by default), otherwise the nexthop is waiting for that lost packet forever.
  \end{itemize}
  \section{Resume a packet}
  After completing a packet transmission, mac will callback the passed handler's function to resume another packet from IFQ. \textit{COPEHandler} is a new class as the common handler, and to handle an event, it will call \textit{COPEPriQueue}'s cope\_prq\_resume function which encapsulates both queues' resume operation.


  \section{TCP Reordering}
  In COPE, there is an \textit{ordering agent}, which ensures that TCP packets are delivered in order. The agent maintains a packet buffer and records the last TCP sequence number passed on to up layer. If the incoming packets that do not produce a hole in the TCP sequence stream are immediately dispatched to the transport layer, and update the state of sequence number in \textit{ordering agent}. Otherwise, they are withheld in the buffer till the gap in the sequence stream is fulled, or until a timer expires.

  \chapter{Summary of Implementing COPE in NS-2}
  \section{Queue Structure}
  \begin{figure}[htb]
    \centering
    \includegraphics[width=3in]{queue_structure.eps}
    \caption{Queue Structure of COPE in NS-2.}
    \label{queue_structure}
  \end{figure}

  IDEAS:

  1. Use \textit{Priqueue} as \textit{OutputQueue} is enough.

  2. Create a new class \textit{VirQueue} which is a child of \textit{PacketQueue}, and add neighbor as an identifier.

  3. \textit{NonAcked Queue} and \textit{AckPending Queue} should be implemented by link list, since its elements need to be deleted arbitrarily. All acks should enter the corresponding queue in order of sequence number, so a common function \textit{enque} is created to handle element insertion with a correct order. For NonAcked Queue, its state will be updated whenever an ack block is received, and the ack block only contain two parameters \textit{last\_ack} and \textit{ack\_map}, so we construct a member function \textit{recvAck} to do this. At the same time, both queues need timers and retransmit counters for each sent packet to schedule retransmission when expired, still thinking about how to realize it.
  

  \section{Function Blocks}
  \begin{figure}[htb]
    \centering
    \includegraphics[width=2in]{function_block.eps}
    \caption{Function blocks of COPE in NS-2.}
    \label{function_block}
  \end{figure}

  \section{NonAckTimer}
  \begin{figure}[htb]
    \centering
    \includegraphics[width=3in]{stop-nonack-timer.eps}
    \caption{How to stop a timer}
    \label{Timer}
  \end{figure}

  \section{NonAckTimer}
  \begin{figure}[htb]
    \centering
    \includegraphics[width=3in]{timers-between-sender-receiver.eps}
    \caption{SendTimer and RecvTimer}
    \label{Timer}
  \end{figure}


  \section{Flow Charts}
  \begin{figure}[htb]
    \centering
    \includegraphics[width=3in]{Sending.eps}
    \caption{Flow charts at the sender's side.}
    \label{Send}
  \end{figure}

  \begin{figure}[htb]
    \centering
    \includegraphics[width=3in]{Recv.eps}
    \caption{Flow charts at the receiver's side.}
    \label{Recv}
  \end{figure}

  \begin{figure}[htb]
    \centering
    \includegraphics[width=3in]{NetworkCoding.eps}
    \caption{Flow chart for Network Coding.}
    \label{NetworkCoding}
  \end{figure}

  \newpage

  \chapter{Terminologies}
  \begin{table}[h]
    \begin{tabular}{|c|c|}
      \hline
      Term & Definition\\
      \hline
      Native Packet & A non-encoded packet\\
      \hline
      Control Packet & Including reception report packet, pure ACK pending packet\\
      \hline
      Codable Packet & \\
      \hline
      Uncodable Packet & Including control packets, \\
      \hline
      Decodable Packet &  \\
      \hline
      Undecodable Packet &  \\
      \hline
    \end{tabular}
  \end{table}

  \newpage

  \begin{thebibliography}{1}
    \providecommand{\url}[1]{#1}
    \csname url@rmstyle\endcsname
    \providecommand{\newblock}{\relax}
    \providecommand{\bibinfo}[2]{#2}
    \providecommand\BIBentrySTDinterwordspacing{\spaceskip=0pt\relax}
    \providecommand\BIBentryALTinterwordstretchfactor{4}
    \providecommand\BIBentryALTinterwordspacing{\spaceskip=\fontdimen2\font plus
      \BIBentryALTinterwordstretchfactor\fontdimen3\font minus
      \fontdimen4\font\relax}
    \providecommand\BIBforeignlanguage[2]{{%
        \expandafter\ifx\csname l@#1\endcsname\relax
        \typeout{** WARNING: IEEEtran.bst: No hyphenation pattern has been}%
        \typeout{** loaded for the language `#1'. Using the pattern for}%
        \typeout{** the default language instead.}%
        \else
        \language=\csname l@#1\endcsname
        \fi
        #2}}

  \bibitem{nc-xor-sigcomm06}
    S.~Katti, H.~Rahul, W.~Hu, D.~Katabi, M.~M\'{e}dard, and J.~Crowcroft, ``{XOR}s
    in the air: Practical wireless network coding,'' in \emph{Proc. SIGCOMM},
    Pisa, Italy, Sep. 2006.

  \bibitem{NC-XOR-Katti-TON-08}
    {S.~Katti, H.~Rahul, W.~Hu, D.~Katabi, M.~Medard, and J.~Crowcroft}, ``{XOR}s
    in the air: Practical wireless network coding,'' \emph{IEEE/ACM Trans. on
      Networking}, vol.~16, no.~3, pp. 497--510, Jun. 2008.

  \bibitem{network-clicktoolkit-mit-00}
    E.~Kohler, robert Morris, B.~Chen, J.~Jannotti, and M.~F. Kaashoek, ``The click
    modular router,'' \emph{ACM Trans. Computer Systems}, Aug. 2000.

  \end{thebibliography}

  \newpage
  \bibliographystyle{IEEEtran}
  \bibliography{../../ref/network-coding,../../ref/sensor-networks,../../ref/network,../../ref/book,../../ref/cellular,../../ref/ref}
\end{CJK*}
\end{document}
